/*
 * @Author: szx
 * @Date: 2022-03-23 13:03:50
 * @LastEditTime: 2022-03-23 13:32:11
 * @Description:
 * @FilePath: \leetcode\剑指offer\19\19.js
 */
/**
 * @param {string} s
 * @param {string} p
 * @return {boolean}
 */
var isMatch = function (s, p) {
    const n = s.length + 1,
        m = p.length + 1,
        //dp[i][j] 代表字符串 s 的前 i 个字符和 p 的前 j 个字符能否匹配。
        dp = new Array(n).fill(0).map(() => new Array(m).fill(0));
    dp[0][0] = true;
    //dp[0][j] = dp[0][j - 2] 且 p[j - 1] = '*'： 
    //首行 s 为空字符串，因此当 p 的偶数位为 * 时才能够匹配
    for (let j = 2; j < m; j += 2) {
        dp[0][j] = dp[0][j - 2] && p[j - 1] == '*';
    }
    for (let i = 1; i < n; i++) {
        for (let j = 1; j < m; j++) {
            if (p[j - 1] == '*') {
                // dp[i][j-2]表示前面那个字符出现0次
                // dp[i - 1][j] && s[i - 1] == p[j - 2] 即让字符 p[j - 2] 多出现 1 次时
                // dp[i - 1][j] && p[j - 2] == '.'即让字符 p[j - 2]='.' 多出现 1 次时
                dp[i][j] = dp[i][j - 2] || (dp[i - 1][j] && (s[i - 1] == p[j - 2] || p[j - 2] == '.'));
            } else {
                dp[i][j] = dp[i - 1][j - 1] && (s[i - 1] == p[j - 1] || p[j - 1] == '.');
            }
        }
    }
    return dp[n - 1][m - 1];
};
